/**
      <one line to give the program's name and a brief idea of what it does.>
    Copyright (C) <2011>  <André Mendes de Oliveira Paiva>

    This program is free software: you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
    the Free Software Foundation, either version 3 of the License, or
    (at your option) any later version.

    This program is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU General Public License for more details.

    You should have received a copy of the GNU General Public License
    along with this program.  If not, see <http://www.gnu.org/licenses/>.
  
 */

package estrutura.hashtable;

import estrutura.EstruturaDados;
import estrutura.No;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileReader;
import java.io.FileWriter;
import java.util.ArrayList;
import java.util.List;

public class HashTable extends EstruturaDados {

    public static final int FATOR_COLISAO = 2;
    public static final int FATOR_ESPALHAMENTO = 10;  

    private List<NoHash> vertices;
    private ArestaHash[] arestas;
    private int fatorColisao = FATOR_COLISAO;
    
    public static final int INDICE_NO_VAZIO = -1;

    public HashTable(String nome, int qtdeNo, int fatorColisao) {
        super(nome);
        this.fatorColisao = fatorColisao;
        int qtdeNoFinal = ((qtdeNo/FATOR_ESPALHAMENTO)+1)*FATOR_ESPALHAMENTO;
        this.setQtdeNo(qtdeNoFinal);
        vertices = new ArrayList<NoHash>(qtdeNoFinal);
        arestas = new ArestaHash[qtdeNoFinal * this.fatorColisao];
    }

    public HashTable(String nome, int qtdeNo) {
        this(nome, qtdeNo, FATOR_COLISAO);
    }

    public HashTable(String nome) {
        this(nome, QTDE_MAX_NO, FATOR_COLISAO);
    }

    public HashTable(int qtdeNo) {
        this(NOME_ESTRUTURA_ANONIMA, qtdeNo, FATOR_COLISAO);
    }

    public HashTable() {
        this(NOME_ESTRUTURA_ANONIMA, QTDE_MAX_NO, FATOR_COLISAO);
    }
    
    /* gerador de valor Hash */
    public int obterHash(int idOrigem, int idDestino)
    {
      int qt_nos_por_parte=(this.getQtdeNo()/FATOR_ESPALHAMENTO);
      
      // Determina o grupo de colisao.
      int grupoColisao = (idDestino % FATOR_COLISAO) * FATOR_ESPALHAMENTO;
      // Determina o grupo de espalhamento.
      int grupoEspalhamento = idOrigem / qt_nos_por_parte;
      // Determina o indice dentro de um grupo de espalhamento.
      int indiceEspalhamento = (idOrigem % qt_nos_por_parte) *
              FATOR_ESPALHAMENTO * FATOR_COLISAO;

      int hash = grupoColisao + grupoEspalhamento + indiceEspalhamento;
      return hash;
    }
    private int obterMaxId()
    {
        int maxId = 0;
        for (NoHash no : vertices)
        {
            if (no == null) break;
            if (no.getId() > maxId) {
                maxId = no.getId();
            }
        }
        return maxId;
    }

    @Override
    public boolean inserirNo(String valor) {
        boolean ret = false;
        int i;
        /* Procura pelo primeiro indice disponivel no vetor */
        for (i = 0; i < vertices.size(); i++) {
            /* quando encontrar o idNo disponível sai do looping */
            if (vertices.get(i) == null) {
                break;
            }
        }
        /*
          se chegou até o fim do looping (fim do vetor) e o vetor já atingiu i
          tamanho máximo, então retorna false
        */
        if (i < this.getQtdeNo()) {
             /* Não é o primeiro No */
            if (i != 0)
            {
               /* determina o proximo do nó anterior */
               vertices.get(i - 1).setIdProximo(i+1);
            }
            /* Cria o nó e adiciona-o ao vetor de vertices */
            NoHash novoNo = new NoHash(this.obterMaxId()+1, valor);
            vertices.add(novoNo);
            ret = true;
        }
        return ret;
    }

    /* Otem um determinado no a partir do ID do Nó */
    public NoHash obterNo(int idNo) {
        NoHash no = null;
        /* Pesquisa o ID do Nó */
        for (int i = 0; i < vertices.size(); i++) {
            if (vertices.get(i).getId() == idNo) {
                no = vertices.get(i);
                break;
            }
        }
        return no;
    }

    /* Otem o indice de um determinado no a partir do ID do Nó */
    @Override
    public int obterIndiceNo(int idNo) {
        int i;
        /* Pesquisa o ID do Nó */
        for (i = 0; i < vertices.size(); i++) {
            if (vertices.get(i).getId() == idNo) {
                break;
            }
        }
        if (i == vertices.size()) {
            i = -1;
        }
        return i;
    }

    /* Obtem o Id do nó Origem, ou seja o nó que não é destino de nenhum outro nó */
    public int obterIDNoOrigem()
    {
       int i, j, id = -1;
       boolean achou ;
       for (i = 0; i < this.vertices.size(); i++)
       {
         achou = false;
         for (j = 0; j < this.arestas.length; j++)
         {
           /* Verifica se o Nó na posição i faz parte de alguma aresta como nó destino */
           if (arestas[j] != null && arestas[j].getIdNoDestino() == this.vertices.get(i).getId()){
              achou = true;
              break;
           }
         }
         if (!achou)
         {
            id = vertices.get(i).getId();
            break;
         }
       }
       return id;
    }
    
    private int obterIndiceAresta (int idNoOrigem, int idNoDestino)
    {
        int hash = this.obterHash(idNoOrigem, idNoDestino);
        int maxIndice = this.getQtdeNo() * FATOR_COLISAO;

        /* procura pela aresta, a partir do indice calculado pela função Hash,
         até que um encontre a Aresta ou encontre uma posição vazia no vetor
         de arestas */

        for(int indice = hash ; indice < maxIndice ; indice++)
        {
            if (arestas[indice] == null)
            {
                return -1;
            }
            
            if (arestas[indice].getIdNoOrigem() == idNoOrigem &&
                arestas[indice].getIdNoDestino() == idNoDestino)
            {
                return indice;
            }
        }

        for(int indice = 0 ; indice < hash && arestas[indice] != null ; indice++)
        {
            if (arestas[indice].getIdNoOrigem() == idNoOrigem &&
                arestas[indice].getIdNoDestino() == idNoDestino)
            {
                return indice;
            }
        }
        
        return -1;
    }

    private int obterProxIndiceDisponivel (int idNoOrigem, int idNoDestino)
    {
        int hash = this.obterHash(idNoOrigem, idNoDestino);
        int maxIndice = this.getQtdeNo() * FATOR_COLISAO;

        /* procura por um indice disponível, a partir do indice calculado pela
         função Hash, até que um encontre a Aresta vazia */

        for(int indice = hash ; indice < maxIndice ; indice++)
        {
            if(arestas[indice] == null || arestas[indice].getAtivo() == false)
            {
                return indice;
            }
                
            if(arestas[indice].getIdNoOrigem() == idNoOrigem &&
               arestas[indice].getIdNoDestino() == idNoDestino)
            {
                return -1;
            }
        }
      
        for(int indice = 0 ; indice < hash ; indice++)
        {
            if(arestas[indice] == null || arestas[indice].getAtivo() == false)
            {
                return indice;
            }
                
            if(arestas[indice].getIdNoOrigem() == idNoOrigem &&
               arestas[indice].getIdNoDestino() == idNoDestino)
            {
                return -1;
            }
        }
        
        return -1;
    }
    
    public ArestaHash obterAresta(int idNoOrigem, int idNoDestino) {
        int ind = this.obterIndiceAresta(idNoOrigem, idNoDestino);
        if (ind != INDICE_NO_VAZIO)
          return arestas[ind];
        else
          return null;
    }
    
    public int obterIdProxAresta(int idNoOrigem, int idNoDestino, int ind)
    {
        int i = ind;
        while (arestas[i] != null)
        {
           i++;
        }
        return i;
    }

    @Override
    public boolean inserirAresta(int idNoOrigem, int idNoDestino) {
        return inserirAresta(idNoOrigem, idNoDestino, null);
    }

    @Override
    public boolean inserirAresta(int idNoOrigem, int idNoDestino, Object rotulo) {
        return inserirAresta(idNoOrigem, idNoDestino, rotulo, 0);
    }

    @Override
    public boolean inserirAresta(int idNoOrigem, int idNoDestino, Object rotulo, int peso)
    {
       boolean ret = false;
       ArestaHash aresta = this.obterAresta(idNoOrigem, idNoDestino);

       /* se não encontrou a aresta */
       if (aresta == null && this.obterIndiceNo(idNoOrigem) != INDICE_NO_VAZIO && this.obterIndiceNo(idNoDestino) != INDICE_NO_VAZIO)
       {
         /* obtem o próximo indice disponível da tabela hash */
         int ind = this.obterProxIndiceDisponivel(idNoOrigem, idNoDestino);
         /* se encontrou um indice válido */
         if (ind != INDICE_NO_VAZIO){
            aresta = new ArestaHash(rotulo, idNoOrigem, idNoDestino, peso);
            this.arestas[ind] = aresta;
            ret = true;
         }
       }
       return ret;
  }

    @Override
    public boolean inserirRotulo(int idNoOrigem, int idNoDestino, Object rotulo) {
       boolean ret = false;
       ArestaHash aresta = this.obterAresta(idNoOrigem, idNoDestino);
       /* se não encontrou a aresta */
       if (aresta != null)
       {
          if (aresta.getRotulo() == null) {
            aresta.setRotulo(rotulo);
            ret = true;
          }
       }
       return ret;
    }

    @Override
    public boolean excluirNo(int idNo) {
        boolean ret = false;
        int indNo = this.obterIndiceNo(idNo);
        /* Se encontrou o nó */
        if (indNo >= 0)
        {
           /* existe mais de um Nó no vetor */
           if (indNo > 0)
           {
              /* é o último nó */
              if (vertices.size() == indNo+1)
                vertices.get(indNo-1).setIdProximo(INDICE_NO_VAZIO);
              else /* anterior do nó a excluir aponta para o próximo nó que será excluído */
                vertices.get(indNo-1).setIdProximo(vertices.get(indNo+1).getId());
                  /* aponta para próximo Nó */
           }
           /* exclui as arestas que tenha como  origem ou destino o nó excluído */
           for(int i = 0; i < arestas.length; i++)
           {
             if (arestas[i] != null && (arestas[i].getIdNoOrigem() == idNo || arestas[i].getIdNoDestino() == idNo))
             {
                /* seta a aresta para inativo - marcando-a como excluída */
                arestas[i].setAtivo(false);
                arestas[i].setIdNoOrigem(INDICE_NO_VAZIO);
                arestas[i].setIdNoDestino(INDICE_NO_VAZIO);
              }
           }
           /* exclui o nó */
           vertices.remove(indNo);
           ret = true;
        }
        return ret;
    }

    @Override
    public boolean excluirRotulo(int idNoOrigem, int idNoDestino) {
        /* verifica se existe aresta */
        boolean ret = false;
        ArestaHash aresta = this.obterAresta(idNoOrigem, idNoDestino);
        if (aresta != null && aresta.getRotulo() != null) {
            aresta.setRotulo(null);
            ret = true;
        }
        return ret;
    }

    @Override
    public boolean excluirAresta(int idNoOrigem, int idNoDestino) {
        /* verifica se existe aresta */
        boolean ret = false;
        ArestaHash aresta = this.obterAresta(idNoOrigem, idNoDestino);
        if (aresta != null)
        {
           /* seta a aresta para inativo - marcando-a como excluída */
           aresta.setAtivo(false);
           aresta.setIdNoOrigem(INDICE_NO_VAZIO);
           aresta.setIdNoDestino(INDICE_NO_VAZIO);
           ret = true;
        }
        return ret;
    }
    
    @Override
    public boolean excluirTodasArestas(int idNoOrigem) {
        boolean ret = false;
        for(int i = 0; i < arestas.length; i++)
        {
           if (arestas[i] != null && arestas[i].getIdNoOrigem() == idNoOrigem)
           {
              /* seta a aresta para inativo - marcando-a como excluída */
              arestas[i].setAtivo(false);
              arestas[i].setIdNoOrigem(INDICE_NO_VAZIO);
              arestas[i].setIdNoDestino(INDICE_NO_VAZIO);
              ret = true;
           }
        }
        return ret;
    }

    @Override
    public void imprimir() {
        int i;
        super.imprimir();
        for (i = 0; i < vertices.size(); i++)
        {
          NoHash noOrigem = vertices.get(i);
          if (vertices.get(i) != null)
          {
            System.out.println(noOrigem.toString());
            System.out.println("  Arestas: ");
            for(int j = 0; j < arestas.length; j++)
            {
                if (arestas[j] != null && arestas[j].getAtivo() && arestas[j].getIdNoOrigem() == noOrigem.getId())
                {
                    NoHash noDestino = this.obterNo(arestas[j].getIdNoDestino());
                    if (noDestino != null)
                      System.out.println("    Valor: " + noDestino.getValor() + " " + (arestas[j].getRotulo() != null ? " - Rotulo: " + arestas[j].getRotulo().toString() : "") );
                }
            }
          }
        }
    }

    public void imprimirNosVizinhos(int id) {
        int i = this.obterIndiceNo(id);
        if (i != -1 && vertices.get(i) != null)
        {
          NoHash noOrigem = vertices.get(i);
          if (vertices.get(i) != null)
          {
            System.out.println("ID: " + noOrigem.getId() + " - Valor: " + noOrigem.getValor());
            System.out.println("  Arestas: ");
            for(int j = 0; j < arestas.length; j++)
            {
                if (arestas[j] != null && arestas[j].getAtivo() && arestas[j].getIdNoOrigem() == noOrigem.getId())
                {
                    NoHash noDestino = this.obterNo(arestas[j].getIdNoDestino());
                    if (noDestino != null)
                      System.out.println("    Valor: " + noDestino.getValor() + (arestas[j].getRotulo() != null ? " - Rotulo: " + arestas[j].getRotulo() : "") );
                }
            }
            System.out.println();
          }
        }
    }
    /* Retorna o idNo da primeira Aresta encontrada ou -1 senão existir aresta*/
    @Override
    public int obterIDPrimeiraAresta(int idNoOrigem) {
        int id = -1;
        for(int i = 0; i < arestas.length; i++)
        {
           /* achou a primeira aresta do nó de origem */
           if (arestas[i] != null && arestas[i].getIdNoOrigem() == idNoOrigem)
           {
             id = arestas[i].getIdNoDestino();
             break;
           }
        }
        return id;
    }

    /* Retorna o id da próxima Aresta encontrada ou -1 se não existir aresta*/
    @Override
    public int obterIDProximaAresta(int idNoOrigem, int idNoDestino)
    {
      int indInicial = this.obterIndiceAresta(idNoOrigem, idNoDestino);
      int maxIndice  = this.getQtdeNo() * FATOR_COLISAO;
      int ind        = indInicial;
      int i          = 0;
      if (indInicial != INDICE_NO_VAZIO)
      {
       /* procura pela próxima aresta, a partir do indice da aresta encontrada */
        while (i < maxIndice && arestas[ind] != null)
        {
          if (arestas[ind].getIdNoOrigem() == idNoOrigem && arestas[ind].getIdNoDestino() != idNoDestino)
            break;
          ind = (indInicial + (++i)) % maxIndice;
        }
      }
      if (i < maxIndice && arestas[ind] != null && arestas[ind].getIdNoOrigem() == idNoOrigem)
        return ind;
      else
        return -1;
    }

    /* Retorna o rotulo da ligação ou null senão não existir aresta*/
    @Override
    public Object obterRotuloAresta(int idNoOrigem, int idNoDestino) {
        ArestaHash aresta = this.obterAresta(idNoOrigem, idNoDestino);
        if (aresta != null)
           return aresta.getRotulo();
        else
           return null;
    }
    /* Obtem o ID de um determinado no a partir do valor Nó */
    public int obterIdPorValor(String valor)
    {
       int i = -1;
        /* Pesquisa o Valor do Nó */
        for (NoHash no : vertices) {
            if (no.getValor().equals(valor)) {
                i = no.getId();
                break;
            }
        }
        return i;
    }
    public boolean obterDadosArquivo(String arquivo)
    {
        boolean res = true;
        String linha;
        try
        {
          FileReader      fr = new FileReader(arquivo);
          BufferedReader  br = new BufferedReader(fr);
          String []nos;      /* vetor de nós, obtido a partir da 1ª linha do arquivo */
          String []arestasArq;  /* vetor de arestas, obtido a partir da 2ª linha do arquivo */
          /* Lê a primeira linha, contendo os nós */
          linha = br.readLine();
          if (linha != null)
          {
            nos =  linha.split(";");
            /* insere os nós */
            for(int i = 0; i < nos.length; i++)
            {
                if (!(nos[i].trim()).equals(""))
                  this.inserirNo(nos[i]);
            }
          }
          int indNoOrigem;
          /* Lê as arestas e inclui as mesmas no grafo */
          while ((linha = br.readLine()) != null)
          {
             arestasArq = linha.split(";");
             /* obtem o ID do nó de origem, a partir do valor do nó */
             indNoOrigem = (this.obterIdPorValor(arestasArq[0]));
             if (indNoOrigem != INDICE_NO_VAZIO)
             {
                for(int i = 1; i < arestasArq.length; i++)
                {
                   /* Se o valor for 1, então é para criar a aresta */
                    if ((arestasArq[i].trim()).equals("1.0"))
                      this.inserirAresta(indNoOrigem, i);
                }
             }
          }
        }
        catch (Exception e)
        {
           System.out.println("Erro ao obter os dados do arquivo: " + e.getMessage());
           res = false;
        }
       return res;
    }
    public boolean gerarArquivoEstrutura(String arquivo)
    {
        boolean res = true;
        String linha="";
        try
        {
          FileWriter      fr = new FileWriter(arquivo);
          BufferedWriter  br = new BufferedWriter(fr);
          int indUltNo = 0;
          /* Lê os nós */
          for (int i = 0; i < vertices.size(); i++ )
          {
             if (vertices.get(i) != null){
               indUltNo = i;
               linha += ";" + vertices.get(i).getValor();
              }
          }
          /* grava a primeira linha do arquivo com os nós */
          br.write(linha);
          NoHash no;
          /* Lê nó e verifica as conexões do mesmo */
          for (int i = 0; i < vertices.size(); i++ )
          {
            no = vertices.get(i);
            if (no != null)
            {
                linha = no.getValor();
                for (int j = 0; j <= indUltNo; j++ )
                {
                   /* se existir aresta, grava 1, caso contrário, grava 0 */
                   if (this.obterAresta(no.getId(), vertices.get(j).getId()) != null)
                     linha += ";" + "1.0";
                   else
                     linha += ";" + "0";
                }
                
                /* grava linha de arestas do nó */
                br.write("\n");
                br.write(linha);
             }
          }
         br.close();
        }
        catch (Exception e)
        {
           System.out.println("Erro ao gravar os dados no arquivo: " + e.getMessage());
           res = false;
        }
       return res;
    }
    /* Obtem o Id do nó Destino, ou seja o nó que não é origem de nenhum outro nó */
    public int obterIDNoDestino()
    {
       int i, j, id = -1;
       boolean achou ;
       for (i = 0; i < this.vertices.size(); i++)
       {
         achou = false;
         for (j = 0; j < this.arestas.length; j++)
         {
           /* Verifica se o Nó na posição i faz parte de alguma aresta como nó destino */
           if (arestas[j] != null && arestas[j].getIdNoOrigem() == this.vertices.get(i).getId()){
              achou = true;
              break;
           }
         }
         if (!achou)
         {
            id = vertices.get(i).getId();
            break;
         }
       }
       return id;
    }

    public ArrayList<No> obterVertices() {
        ArrayList <No> listaNo = new ArrayList<No>();
        for(int i = 0; i < vertices.size(); i++)
            if (vertices.get(i) != null)
               listaNo.add(vertices.get(i));
       return listaNo;
    }
    public ArrayList<No> obterNosVizinhos(int idNo)
    {
        ArrayList <No> listaNo = new ArrayList<No>();
        NoHash no = this.obterNo(idNo);
        if (no != null)
        {
           for (int i = 0; i < arestas.length; i++)
             if (arestas[i] != null && arestas[i].getAtivo() && arestas[i].getIdNoOrigem() == idNo){
                 no = this.obterNo(arestas[i].getIdNoDestino());
                 listaNo.add(no);
               }
        }
        return listaNo;
    }

    public No obterNoPorID(int idNo)
    {
       return this.obterNo(idNo);
    }
}
